#include "boostDefs.h"
#include "clear-iterator.h"
#include "graph.hh"
#include <set>
#include <iostream>
#include <utility>
#include <algorithm>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>

using namespace std;

int sum = 0;

// Convert a graph stored in the Boost library format to the Bliss library format
bliss::Graph boostToBliss(BoostGraph const &g)
{
	int verts = num_vertices(g);
	bliss::Graph retGraph(verts);
	pair<bedge_iterator,bedge_iterator> iters = edges(g);
	int v1, v2;
	while (iters.first != iters.second)
	{
		v1 = source(*iters.first,g);
		v2 = target(*iters.first,g);
		retGraph.add_edge(v1,v2);
		++iters.first;
	}
	return retGraph;
}

// Copy the edges of inGraph into those of outGraph
void copyEdges(BoostGraph const &inGraph, BoostGraph &outGraph)
{
	pair<bedge_iterator,bedge_iterator> iters = edges(inGraph);
	while (iters.first != iters.second)
	{
		add_edge(source(*iters.first,inGraph),target(*iters.first,inGraph),outGraph);
		++iters.first;
	}
}

// Return the BoostGraph representing the union of g1 and g2
void graphUnion(BoostGraph &outGraph, BoostGraph const &g1, BoostGraph const &g2)
{
	// simply combine the edge sets
	copyEdges(g1,outGraph);
	copyEdges(g2,outGraph);
}

// Return a copy of g such that all edges containing either vert1 or vert2 are removed
BoostGraph removeVerts(BoostGraph const &g, int vert1, int vert2)
{
    int v1, v2;
    BoostGraph retGraph;
    pair<bedge_iterator,bedge_iterator> iters = edges(g);
    while (iters.first != iters.second)
    {
        v1 = source(*iters.first,g);
        v2 = target(*iters.first,g);
        if (v1 != vert1 && v1 != vert2 && v2 != vert1 && v2 != vert2)
            add_edge(v1,v2,retGraph);
        ++iters.first;
     }
     return retGraph;
}

void complement(BoostGraph &copyOfUniverse, BoostGraph &toExclude) {
	pair<bedge_iterator,bedge_iterator> edge_iters = edges(toExclude);
	while (edge_iters.first != edge_iters.second) {
		vert_descriptor a,b;
		a = source(*edge_iters.first,toExclude);
		b = target(*edge_iters.first,toExclude);
		remove_edge(a,b,copyOfUniverse);
		edge_iters.first++;
	}
}

// Recursive function to find all one factors of a given graph.
// For the initial call, unused should be the graph whose one-factors need to be found, used an empty graph and
// one_factors a vector of BoostGraphs that will contain the output one-factors
void findOneFactors(BoostGraph const &unused, BoostGraph& used, vector<BoostGraph>& one_factors)
{
    int start_v, end_v;
    // Base case
    if (num_edges(unused) == 0)
    {
		one_factors.push_back(used);
    	++sum;
    	return;
    }
    pair<bedge_iterator,bedge_iterator> edge_iters = edges(unused);
    start_v = source(*edge_iters.first,unused);
    pair<badj_iterator,badj_iterator> adj_iters = adjacent_vertices(start_v,unused);
    while (adj_iters.first != adj_iters.second)
    {
        end_v = *adj_iters.first;
        // Need start and end ClearIterator for creating unused copy without start_v, end_v
        //ClearIterator clearIterStart(edge_iters.first,edge_iters.second,start_v,end_v,&unused);
        //ClearIterator clearIterEnd(edge_iters.second,edge_iters.second,start_v,end_v,&unused);
        //Graph unusedPrime = Graph(clearIterStart,clearIterEnd,num_vertices(unused)-2);
        BoostGraph unusedPrime = removeVerts(unused,start_v,end_v);
        add_edge(start_v,end_v,used);
        findOneFactors(unusedPrime,used,one_factors);
        remove_edge(start_v,end_v,used);
        ++adj_iters.first;
    }
}

int main(int argc, char* argv[])
{
	if (argc != 2)
	{
		cout << "Enter number of vertices" << endl;
		exit(1);
	}

	int num_verts = atoi(argv[1]);
	BoostGraph g(num_verts);
	BoostGraph used;
	vector<BoostGraph> one_factors;

	// Create a num_verts-regular fully connected graph
	for (int i=0; i<num_verts; i++)
	{
		for (int j=i+1; j<num_verts; j++)
		{
			add_edge(i,j,g);
		}
	}

	findOneFactors(g,used,one_factors);
	cout << sum << " one factors in K" << num_verts << endl;
	vector<BoostGraph>::iterator iter = one_factors.begin();
	while (iter != one_factors.end())
	{
		pair<bedge_iterator,bedge_iterator> eiters = edges(*iter);
		while (eiters.first != eiters.second)
		{
			cout << "(" << source(*eiters.first,*iter) << "," << target(*eiters.first,*iter) << ")";
			++eiters.first;
		}
		cout << endl;
		++iter;
	}
	
	return 0;
}

/*
int main(int argc, char* argv[])
{
	bliss::Heap myheap;
	myheap.init(5);
	cout << myheap.is_empty() << endl;
   if (argc != 2)
   {
      cout << "Enter number of vertices" << endl;
      exit(1);
   }

   int num_verts = atoi(argv[1]);
   BoostGraph g(num_verts);
   BoostGraph used;
   vector<BoostGraph> one_factors;

   // Create a num_verts-regular fully connected graph
   for (int i=0; i<num_verts; i++)
   {
      for (int j=i+1; j<num_verts; j++)
      {
            add_edge(i,j,g);
      }
   }
	BoostGraph h(num_verts);
   for (int half=0; half<num_verts; half += num_verts/2) {
		for (int i=0; i<num_verts/2; ++i) {
			for (int j=1; j<num_verts/2; ++j) {
				add_edge(half+i,half+j,h);
			}
		}
   }
	cout <<"We didn't fail yet!"<<endl;
	complement2(g,h);
	cout<<"we probably fail before this?"<<endl;
   findOneFactors(g,used,one_factors);
   cout << sum << " one factors in K" << num_verts << endl;
   return 0;
}*/
